{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Activité : k plus proches voisins - Classification de fruits\n\nDans cet exercice, vous allez classifier un fruit inconnu à partir d'un ensemble d'apprentissage plus grand. Vous allez :\n\n1. Calculer la distance euclidienne entre le fruit inconnu et chaque fruit de l'ensemble d'apprentissage.\n2. Trier les distances à l'aide d'un tri par sélection.\n3. Sélectionner les k plus proches voisins et effectuer un vote majoritaire pour déterminer la classe prédite.\n4. Visualiser l'ensemble d'apprentissage sur un graphique.\n5. Répondre à la question bonus : que faire si k est pair ?"},{"metadata":{},"cell_type":"markdown","source":"## Données\n\nNous disposons de l'ensemble d'apprentissage suivant (ensemble plus grand) :\n\n```python\nensemble_apprentissage = [\n    {\"fruit\": \"Pomme\", \"poids\": 150, \"texture\": 4},\n    {\"fruit\": \"Pomme\", \"poids\": 170, \"texture\": 5},\n    {\"fruit\": \"Pomme\", \"poids\": 130, \"texture\": 3},\n    {\"fruit\": \"Pomme\", \"poids\": 155, \"texture\": 4},\n    {\"fruit\": \"Pomme\", \"poids\": 160, \"texture\": 6},\n    {\"fruit\": \"Orange\", \"poids\": 160, \"texture\": 7},\n    {\"fruit\": \"Orange\", \"poids\": 140, \"texture\": 8},\n    {\"fruit\": \"Orange\", \"poids\": 155, \"texture\": 9},\n    {\"fruit\": \"Orange\", \"poids\": 145, \"texture\": 7},\n    {\"fruit\": \"Orange\", \"poids\": 150, \"texture\": 8},\n    {\"fruit\": \"Orange\", \"poids\": 165, \"texture\": 7},\n    {\"fruit\": \"Pomme\", \"poids\": 135, \"texture\": 4}\n]\n\nfruit_inconnu = {\"poids\": 148, \"texture\": 6}\n```"},{"metadata":{"trusted":true},"cell_type":"code","source":"ensemble = [\n    {\"fruit\": \"Pomme\", \"poids\": 150, \"texture\": 4},\n    {\"fruit\": \"Pomme\", \"poids\": 170, \"texture\": 5},\n    {\"fruit\": \"Pomme\", \"poids\": 130, \"texture\": 3},\n    {\"fruit\": \"Pomme\", \"poids\": 155, \"texture\": 4},\n    {\"fruit\": \"Pomme\", \"poids\": 160, \"texture\": 6},\n    {\"fruit\": \"Orange\", \"poids\": 160, \"texture\": 7},\n    {\"fruit\": \"Orange\", \"poids\": 140, \"texture\": 8},\n    {\"fruit\": \"Orange\", \"poids\": 155, \"texture\": 9},\n    {\"fruit\": \"Orange\", \"poids\": 145, \"texture\": 7},\n    {\"fruit\": \"Orange\", \"poids\": 150, \"texture\": 8},\n    {\"fruit\": \"Orange\", \"poids\": 165, \"texture\": 7},\n    {\"fruit\": \"Pomme\", \"poids\": 135, \"texture\": 4}\n]\n\nfruit_inconnu = {\"poids\": 148, \"texture\": 6}","execution_count":1,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"import matplotlib.pyplot as plt\n\npoids_pomme = [fruit[\"poids\"] for fruit in ensemble if fruit[\"fruit\"] == \"Pomme\"]\ntexture_pomme = [fruit[\"texture\"] for fruit in ensemble if fruit[\"fruit\"] == \"Pomme\"]\npoids_orange = [fruit[\"poids\"] for fruit in ensemble if fruit[\"fruit\"] == \"Orange\"]\ntexture_orange = [fruit[\"texture\"] for fruit in ensemble if fruit[\"fruit\"] == \"Orange\"]\nplt.scatter(fruit_inconnu[\"poids\"], fruit_inconnu[\"texture\"], c='blue', label='Fruit inconnu', marker='x', s=100)\n\n\nplt.scatter(poids_pomme, texture_pomme, c='red', label='Pomme')\nplt.scatter(poids_orange, texture_orange, c='orange', label='Orange')\nplt.xlabel('Poids')\nplt.ylabel('Texture')\nplt.legend()\nplt.show()","execution_count":2,"outputs":[{"output_type":"display_data","data":{"application/javascript":"element.append(window._basthonBypassBus.pop(0));"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"## Question 1\n\nÉcrire une fonction `distance_euclidienne` qui calcule la distance euclidienne entre deux fruits en utilisant leurs attributs \"poids\" et \"texture\"."},{"metadata":{"trusted":true},"cell_type":"code","source":"import math\n\ndef distance_euclidienne(a, b):\n    return math.sqrt((a[\"poids\"] - b[\"poids\"])**2 + (a[\"texture\"] - b[\"texture\"])**2)","execution_count":3,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Question 2\n\nImplémentez une fonction `selection_sort` qui trie une liste de tuples de la forme `(distance, fruit)` par ordre croissant de distance."},{"metadata":{"trusted":true},"cell_type":"code","source":"def selection_sort(liste):\n    n = len(liste)\n    for i in range(n):\n        min_index = i\n        for j in range(i + 1, n):\n            if liste[j][0] < liste[min_index][0]:\n                min_index = j\n        liste[i], liste[min_index] = liste[min_index], liste[i]\n    return liste","execution_count":4,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"#test\ndef list_distance(liste, fruit_inconnu):\n    distances = []\n    for element in liste:\n            d = distance_euclidienne(element, fruit_inconnu)\n            distances.append((d, element[\"fruit\"]))\n    distances = selection_sort(distances)\n    return distances\n\nlist_distance(ensemble, fruit_inconnu)","execution_count":5,"outputs":[{"output_type":"execute_result","execution_count":5,"data":{"text/plain":"[(2.8284271247461903, 'Pomme'), (2.8284271247461903, 'Orange'), (3.1622776601683795, 'Orange'), (7.280109889280518, 'Pomme'), (7.615773105863909, 'Orange'), (8.246211251235321, 'Orange'), (12.0, 'Pomme'), (12.041594578792296, 'Orange'), (13.152946437965905, 'Pomme'), (17.029386365926403, 'Orange'), (18.24828759089466, 'Pomme'), (22.02271554554524, 'Pomme')]"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"## Question 3\n\nImplémentez la fonction `kNN` qui :\n- Calcule la distance entre le fruit inconnu et chaque fruit de l'ensemble d'apprentissage.\n- Trie les distances à l'aide de `selection_sort`.\n- Sélectionne les k plus proches voisins.\n- Effectue un vote majoritaire pour déterminer la classe prédite (sans utiliser `Counter`)."},{"metadata":{"trusted":true},"cell_type":"code","source":"def kNN(ensemble,fruit_inconnu, k):\n    distances = list_distance(ensemble, fruit_inconnu)\n    print(distances)\n    \n    k_voisins = [item[1] for item in distances[:k]]\n    print(k_voisins)\n    \n    classes = {}\n    for v in k_voisins:\n        if v in classes:\n            classes[v] += 1\n        else:\n            classes[v] = 1\n    print(classes)\n    \n    classe_majoritaire = \"\"\n    max_count = 0\n    for fruit, count in classes.items():\n        if count > max_count:\n            max_count = count\n            classe_majoritaire = fruit\n    return classe_majoritaire\n\n\n# test\nk = 3\nclasse_predite = kNN(ensemble, fruit_inconnu, k)\nprint(\"Le fruit inconnu est classé comme une\", classe_predite)","execution_count":6,"outputs":[{"output_type":"stream","text":"[(2.8284271247461903, 'Pomme'), (2.8284271247461903, 'Orange'), (3.1622776601683795, 'Orange'), (7.280109889280518, 'Pomme'), (7.615773105863909, 'Orange'), (8.246211251235321, 'Orange'), (12.0, 'Pomme'), (12.041594578792296, 'Orange'), (13.152946437965905, 'Pomme'), (17.029386365926403, 'Orange'), (18.24828759089466, 'Pomme'), (22.02271554554524, 'Pomme')]\n['Pomme', 'Orange', 'Orange']\n{'Pomme': 1, 'Orange': 2}\nLe fruit inconnu est classé comme une Orange\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"## Question 6\n\nLorsque k est pair, il peut arriver qu'il y ait autant de voisins pour chaque classe, ce qui conduit à une égalité dans le vote majoritaire. Par exemple, avec k = 4, on obtient :\n\n```\n[(2.8284271247461903, 'Pomme'), (2.8284271247461903, 'Orange'), (3.1622776601683795, 'Orange'), (7.280109889280518, 'Pomme'), ...]\n['Pomme', 'Orange', 'Orange', 'Pomme']\n{'Pomme': 2, 'Orange': 2}\n```\n\nDans notre implémentation, la classe retournée est \"Pomme\" car c'est la première rencontrée lors de l'itération sur le dictionnaire. Pour pallier ce problème, il est recommandé de choisir un k impair. Sinon, on peut ajouter une règle de départage.\n\nPar exemple, en cas d'égalité, on peut retourner la classe du voisin le plus proche parmi.\nC'est à dire, on cherche parmi le fruit avec la distance  minimale.\nComment trouver ce fruit ?"},{"metadata":{"trusted":true},"cell_type":"code","source":"print(list_distance(ensemble, fruit_inconnu)[0])","execution_count":7,"outputs":[{"output_type":"stream","text":"(2.8284271247461903, 'Pomme')\n","name":"stdout"}]}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}},"nbformat":4,"nbformat_minor":2}